This invention relates to the scheduling, within multimedia database servers, of resources for storing or transmitting composite multimedia objects that contain various forms of multimedia data such as images, video, and audio.
Next generation database systems will need to provide support (for example, identify the storage (memory) and disk or transmission bandwidth requirements) for various forms of multimedia data such as images, video, and audio. These new data types differ from conventional alphanumeric data in their characteristics, and hence require different techniques for their organization and management. A fundamental issue is that digital video and audio streams consist of a sequence of media quanta (for example, video frames and audio samples) which convey meaning only when presented continuously in time. Hence, a multimedia database server needs to provide a guaranteed level of service for accessing such continuous media (CM streams in order to satisfy their pre-specified real-time delivery rates and ensure intra-media continuity. Given the limited amount of resources (for example, memory and disk or transmission bandwidth), it is a challenging problem to design effective resource scheduling algorithms that can provide on-demand support for a large number of concurrent continuous media clients.
An important requirement for multimedia database systems is the ability to dynamically compose new multimedia objects from an existing repository of CM streams. Temporal and spatial primitives specifying the relative timing and output layout of component CM streams provide perhaps the most powerful and natural method of authoring such composite multimedia presentations. Thus, to compose tailored multimedia presentations, a user might define temporal dependencies among multiple CM streams having various length and display bandwidth requirements. For example, a story for the evening news can start out by displaying a high resolution video clip with concurrent background music and narration added after an initial delay. After some time into the story, the video screen is split and a new video clip starts playing on the left half of the screen. After the second video clip ends, the narration stops and the story comes to a conclusion with the display of the first clip and the background music.
In the presence of such composite multimedia objects, a scheduling algorithm must ensure that the inter-media synchronization constraints defined by the temporal relationships among CM components are met. Handling these synchronization constraints requires a task model that is significantly more complex than the models employed in scheduling theory and practice. See, Soumen Chakrabarti and S. Muthukrishnan, xe2x80x9cResource Scheduling for Parallel Database and Scientific Applicationsxe2x80x9d, Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 329-335, Padua, Italy, June 1996; M. R. Garey and R. L. Graham, xe2x80x9cBounds for Multiprocessor Scheduling with Resource Constraintsxe2x80x9d, SIAM Journal on Computing, 4(2):187-200, June 1975; and M. R. Garey, R. L. Graham, D. S. Johnson, and Andrew Chi-Chih Yao, xe2x80x9cResource Constrained Scheduling as Generalized Bin Packingxe2x80x9d, Journal of Combinatorial Theory (A), 21:257-298, 1976. More specifically, composite multimedia objects essentially correspond to resource-constrained tasks with time-varying resource demands. Resource constraints come from the limited amount of server resources available to satisfy the requirements of CM streams and time-variability stems from the user-defined inter-media synchronization requirements. We believe that this is a task model that has not been previously studied in the context of deterministic scheduling theory. Furthermore, despite the obvious importance of the problem for multimedia database systems, our work appears to be the first systematic study of the problems involved in scheduling multiple composite multimedia objects. We suspect that this may be due to the difficulty of the problems, most of which are non-trivial generalizations of NP-hard optimization problems.
It appears that today""s multimedia storage servers offer no clever scheduling support for composite multimedia presentations. The approach typically employed is to reserve server resources based on the maximum (that is, worst-case) resource demand over the duration of a composite presentation. Examples of systems using this worst-case resource reservation method include the Fellini and CineBlitz multimedia storage servers developed at Bell Laboratories and discussed in Cliff Martin, P. S. Narayanan, Banu xc3x96zden, Rajeev Rastogi, and Avi Silberschatz, xe2x80x9cThe Fellini Multimedia Storage Serverxe2x80x9d, Multimedia Information Storage and Management, pages 117-146, (S. M. Chung ed., Kluwer Academic Publishers 1996); Starlight""s StarWorks (http://www.starlight.com/); and Oracle""s Media Server (http://www.oracle.com/). Conceptually, this approach is equivalent to identifying the resource requirements of the presentation over time with their enclosing Minimum Bounding Rectangle MBR). Although this simplification significantly reduces the complexity of the relevant scheduling problems, it suffers from two major deficiencies.
The volume (that is, resource-time product as in Chakrabarti et al. and in our Minos N. Garofalakis and Yannis E. Ioannidis, xe2x80x9cParallel Query Scheduling and Optimization with Time- and Space-Shared Resourcesxe2x80x9d, Proceedings of the 23rd International Conference on Very Large Data Bases, pages 296-305, Athens, Greece, August 1997. ) in the enclosing MBR can be significantly larger than the actual requirements of the composite object. This can result in wasting large fractions of precious server resources, especially for relatively xe2x80x9csparsexe2x80x9d composite objects.
The MBR simplification xe2x80x9chidesxe2x80x9d the timing structure of individual streams from the scheduler, making it impossible to improve the performance of a schedule through clever use of memory buffers.
A number of conceptual models have been developed for capturing the temporal aspects of multimedia data. They can be roughly classified into three categories, namely: 1) graph-based models (for example, object composition petri nets as in Thomas D. C. Little and Arif Ghafoor, xe2x80x9cSynchronization and Storage Models for Multimedia Objectsxe2x80x9d, IEEE Journal on Selected Areas in Communications, 8 (3):413-427, April 1990 and presentation graphs as in Kingsley C. Nwosu, Bhavani Thuraisingham, and P. Bruce Berra, eds., Multimedia Database Systems: Design and Implementation Strategies, Kluwer Academic Publishers, 1996); 2) language-based models (for example, HyTime as in Steven R. Newcomb, Neill A. Kipp, and Victoria T. Newcomb, xe2x80x9cThe HyTime Hypermedia/Time-based Document Structuring Languagexe2x80x9d, Communications of the ACM, 34 (11), November 1991 and MHEG as in R. Price, xe2x80x9cMHEG: An Introduction to the Future International Standard for Hypermedia Object Interchangexe2x80x9d, Proceedings of ACM Multimedia ""93, pages 121-128, Anaheim, Calif., August 1993.), and 3) temporal abstraction models (for example, temporal intervals and relations as in J. F. Allen, xe2x80x9cMaintaining Knowledge About Temporal Intervalsxe2x80x9d, Communications of the ACM, 26(11):832-843, November 1983, and Thomas D. C. Little and Arif Ghafoor, xe2x80x9cInterval-Based Conceptual Models for Time-Dependent Multimedia Dataxe2x80x9d, IEEE Transactions on Knowledge and Data Engineering, 5(4):551-563, August 1993). Candan et al. present a method based on linear difference constraints for defining flexible inter-media synchronization requirements and show how these constraints can be solved and/or modified to ensure consistency in K. Selcuk Candan, B. Prabhakaran and V. S. Subrahmanian, xe2x80x9cRetrieval Schedules Based on Resource Availability and Flexible Presentation Specificationsxe2x80x9d, Technical Report CS-TR-3616, University of Maryland, College Park, 1996. Thimm et al. describe a feedback-based architecture for adapting a multimedia presentation to the changes in resource availability by modifying the presentation quality in Heiko Thimm and Wolfgang Klas, xe2x80x9cxcex4-Sets for Optimized Reactive Adaptive Playout Management in Distributed Multimedia Database Systemsxe2x80x9d, Proceedings of the Twelfth International Conference on Data Engineering, pages 584-592, New Orleans, La., February 1996. In our earlier work, Minos N. Garofalakis and Yannis E. Ioannidis, xe2x80x9cScheduling Issues in Multimedia Query Optimizationxe2x80x9d: ACM Computing Surveys, 27(4):590-592, December 1995 (Symposium on Multimedia), we present a scheduling framework for simple (independent) CM streams based on the resource-constrained list-scheduling methodology of Garey and Graham discussed above.
Articles which address some of the issues in scheduling composite multimedia objects include Surajit Chaudhuri, Shahram Ghandeharizadeh and Cyrus Shahabi, xe2x80x9cAvoiding Retrieval Contention for Composite Multimedia Objectsxe2x80x9d, Proceedings of the 21st International Conference on Very Large Data Bases, pages 287-298, Zurich, Switzerland, September 1995; and Cyrus Shahabi, Shahram Ghandeharizadeh and Surajit Chaudhuri, xe2x80x9cOn Scheduling Atomic and Composite Multimedia Objectsxe2x80x9d, Technical Report USC-CS-95-622, University of Southern California, 1995, (to appear in IEEE Transactions on Knowledge and Data Engineering). However, their research on composite objects focuses on (1) using memory to resolve the problem of xe2x80x9cinternal contentionxe2x80x9d, which occurs when the temporal synchronization constraints cause stream retrievals for a single object to collide; and, (2) developing heuristic memory management policies to distribute a fixed amount of server memory among multiple competing objects. More specifically, Chaudhuri et al. suggest a conservative and a greedy heuristic for allocating memory among multiple binary composite objects, under the assumption of regular, round-robin striping of component streams. However, extending their heuristics to general, n-ary objects appears to be problematic. Shahabi et al. show how these conservative and greedy methods can be adapted to the problem of resolving internal contention in a single n-ary composite object, again assuming round-robin layout. Although the authors outline some ideas on how to actually schedule multiple composite objects, they offer no concrete algorithmic solutions for the problem. Furthermore, their development is based on the assumption of a round-robin distribution of stream fragments across disks, whereas we assume a more abstract xe2x80x9cblack-boxxe2x80x9d model of server disk bandwidth.
Thus, there remains in the art a need to implement a composite multimedia object scheduling system that permits the efficient and reliable scheduling of the composite multimedia objects to ensure that the inter-media synchronization constraints between the CM streams are met.
We formulate resource scheduling problems for composite multimedia objects and develop novel efficient scheduling algorithms, drawing on a number of techniques from pattern matching and multiprocessor scheduling. Our formulation is based on a novel sequence packing problem, where the goal is to superimpose numeric sequences (representing the objects"" resource needs as a function of time) within a fixed capacity bin (representing the server""s resource capacity). We propose heuristic algorithms for the sequence packing problem using a two-step approach. First, we present a xe2x80x9cbasic stepxe2x80x9d method for packing two object sequences into a single, combined sequence. Second, we show how this basic step can be employed within different scheduling heuristics to obtain a playout schedule for multiple composite objects. More specifically, we examine greedy scheduling heuristics based on the general list-scheduling (LS) methodology of Graham in R. L. Graham, xe2x80x9cBounds on Multiprocessing Timing Anomaliesxe2x80x9d, SIAM Journal on Computing, 17(2):416-429, March 1969; and in Garey and Graham. We show that although LS schemes are provably near-optimal for packing monotonic sequences, they can have poor worst-case performance when the monotonicity assumption is violated. A xe2x80x9cmonotonicxe2x80x9d sequence is a sequence in which the bandwidth requirement of the sequence can either increase or decrease over time, but it can not do both. Based on this result, we propose: (1) inventive methods for improving the behavior of simple LS through the use of extra memory buffers; and, (2) a novel family of more clever scheduling algorithms, termed list-scheduling with backtracking (LSB), that try to improve upon simple LS by occasional local improvements to the schedule.
Results with randomly generated composite objects show that our LS strategy offers excellent average-case performance compared to both an MBR-based approach and the optimal solution. Finally, we show how the idea of stream sharing can be exploited to improve the quality of a schedule. xe2x80x9cStream sharingxe2x80x9d occurs when we allow several presentations to share component streams from separate composite objects.
Although our invention is primarily geared towards composite objects, our task model also exactly captures the problem of scheduling the retrievals of variable bit rate streams, that is, CM streams whose bandwidth requirements can vary over time. This is a very important application of our scheduling framework, since real-life CM data is nearly always variable rate.
Therefore, there is a need for our inventive method of scheduling the provision of composite multimedia objects, each comprising one or more continuous media streams of audio data, video data and other data, where the continuous media streams are of varying bandwidth requirement and duration; generating composite multimedia objects from the continuous media streams; and determining a run-length compressed form for each of the generated composite multimedia objects. Where the other data can be still images (for example, photographs), other images (for example, graphic and scanned images), animations, text, and program code data files)